package gold.digger;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC649 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public String predictPartyVictory(String senate) {
            boolean[] isInvalid = new boolean[senate.length()];
            // Radiant(天辉)和 Dire(夜魇)
            TreeSet<Integer> rCount = new TreeSet<>(), dCount = new TreeSet<>();
            for (int i = 0; i < senate.length(); i++) {
                if (senate.charAt(i) == 'R') rCount.add(i);
                else dCount.add(i);
            }

            while (rCount.size() > 0 && dCount.size() > 0) {
                for (int i = 0; i < senate.length(); i++) {
                    if (isInvalid[i]) continue;
                    if (senate.charAt(i) == 'R') {
                        if (dCount.size() <= 0) return "Radiant";
                        else {
                            Integer afterNearestD = dCount.ceiling(i);
                            int toRemoveIdx = null == afterNearestD ? dCount.first() : afterNearestD.intValue();
                            isInvalid[toRemoveIdx] = true;
                            dCount.remove(toRemoveIdx);
                        }
                    } else {
                        if (rCount.size() <= 0) return "Dire";
                        else {
                            Integer afterNearestD = rCount.ceiling(i);
                            int toRemoveIdx = null == afterNearestD ? rCount.first() : afterNearestD.intValue();
                            isInvalid[toRemoveIdx] = true;
                            rCount.remove(toRemoveIdx);
                        }
                    }
                }
            }

            return rCount.size() > 0 ? "Radiant" : "Dire";
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.predictPartyVictory("RDD"));
    }

    public static void main(String[] args) throws Exception {
        LC649 an = new LC649();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
